LISP

LISP is one of the simplest computer languages in terms of syntax and semantics, and also one of the most powerful. It was developed in the mid-1950's by John McCarthy at M.I.T. as a "LISt Processing language."

It has been historically used for virtually all Artificial Intelligence programs and is often the environment of choice for applications which require a powerful interactive working environment.

LISP presents a very different way to think about programming from the "algorithmic" languages, such as Python, C++, and Java.

Basic Functions (SET, SETQ, EVAL, ATOM)

We may assign values to variables using the function SET.

For example, the statement (SET 'test 6) would have a value of a 6, and (more importantly, however) would also cause the atom 'test to be bound to the atom 6.

The function SETQ is the same as SET, but it causes LISP to act as if the first argument was quoted. Observe the following examples:

Statement	Value	Comment
(SET 'a (MULT 2 3))	6	a is an atom with a value of 6
(SET 'a '(MULT 2 3))	(MULT 2 3)	a is a list with 3 elements
(SET 'b 'a)	a	b is an atom with a value of the character a
(SET 'c a)	(MULT 2 3)	c is a list with 3 elements
(SETQ EX (ADD 3 (MULT 2 5)))	13	The variable EX has a value of 13
(SETQ VOWELS '(A E I O U))	(A E I O U)	VOWELS is a list of 5 elements

The function EVAL returns the value of its argument, after it has been evaluated.

For example, (SETQ z '(ADD 2 3)) has a value of the list (ADD 2 3); the function (EVAL 'z) has a value of (ADD 2 3); the function (EVAL z) has a value of 5 (but the binding of the atom z has not changed).

In this last example, you can think of z being "resolved" twice: once because it is an argument to a function and LISP evaluates all arguments to functions before the function is invoked, and once when the function EVAL is invoked to resolve arguments.

The function ATOM can be used to determine whether an item is an atom or a list. It returns either "true", or "NIL" for false. Consider the following examples:

Statement	Value	Comment
(SETQ p '(ADD 1 2 3 4))	(ADD 1 2 3 4)	p is a list with 5 elements
(ATOM 'p)	true	The argument to ATOM is the atom p
(ATOM p)	NIL	Because p is not quoted, it is evaluated to the 5-element list.
(EVAL p)	10	The argument to EVAL is the value of p; the value of p is 10.

List Functions (CAR, CDR, CONS, REVERSE)

The two most famous LISP functions are CAR and CDR (pronounced: could-er), named after registers of a now long-forgotten IBM machine on which LISP was first developed.

The function (CAR x) returns the first item of the list x (and x must be a list or an error will occur); (CDR x) returns the list without its first element (again, x must be a list).

The function CONS takes two arguments, of which the second must be a list.

It returns a list which is composed by placing the first argument as the first element in the second argument's list.

The function REVERSE returns a list which is its arguments in reverse order.

The CAR and CDR functions are used extensively to grab specific elements of a list or sublist, that there's a shorthand for this: (CADR x) is the same as (CAR (CDR x)), which retrieves the second element of the list x; (CAADDAR x) is a shorthand for (CAR (CAR (CDR (CDR (CAR x))))), and so on.

The following examples illustrate the use of CAR, CDR, CONS, and REVERSE:

Statement	Value
(CAR '(This is a list))	This
(CDR '(This is a list))	(is a list)
(CONS 'red '(white blue))	(red white blue)
(SETQ z (CONS '(red white blue) (CDR '(This is a list))))	((red white blue) is a list)
(REVERSE z)	(list a is (red white blue))
(CDDAR z)	(blue)

Arithmetic Functions (ADD, MULT, ...)

As you have probably already figured out, the function ADD simply summed its arguments.

We'll also be using the following arithmetic functions:

Function	Result
(ADD x1 x2 …)	sum of all arguments
(SUB a b)	a-b
(MULT x1 x2 …)	product of all arguments
(DIV a b)	a/b
(SQUARE a)	a*a
(EXP a n)	an
(EQ a b)	true if a and b are equal, NIL otherwise
(POS a)	true if a is positive, NIL otherwise
(NEG a)	true if a is negative, NIL otherwise

Functions ADD, SUB, MULT, and DIV can be written as their common mathematical symbols, +, -, *, and /. Here are some examples of these functions:

Statement	Value
(ADD (EXP 2 3) (SUB 4 1) (DIV 54 4))	24.5
(- (* 3 2) (- 12 (+ 1 2 1)))	-2
(ADD (SQUARE 3) (SQUARE 4))	25

User-defined Functions

LISP also allows us to create our own functions using the DEF function. (We will sometimes use DEFUN rather than DEF, as it is a bit more standard terminology.) For example,

(DEF SECOND (args) (CAR (CDR args)))

defines a new function called SECOND which operates on a single parameter named "args".

SECOND will take the CDR of the parameter and then the CAR of that result.

So, for example: (SECOND '(a b c d e)) would first CDR the list to give (b c d e), and then CAR that value returning the single character "b". Consider the following program fragment:

(SETQ X '(a c s l))
(DEF WHAT(args) (CONS args (REVERSE (CDR args))))
(DEF SECOND(args) (CONS (CAR (CDR args)) NIL))

The following chart illustrates the use of the user-defined functions WHAT and SECOND:

Statement	Value
(WHAT X)	((a c s l) l s c)
(SECOND X)	(c)
(SECOND (WHAT X))	(l)
(WHAT (SECOND X))	((c))

Online Interpreters

There are many online LISP interpreters available on the Internet.

The one that ACSL uses for testing its programs is CLISP that is accessible from JDoodle.

This interpreter is nice because it is quite peppy in running programs, and functions are not case sensitive.

So, (CAR (CDR x)) is legal as is (car (cdr x)) One drawback of this interpreter is the print function changes lowercase input into uppercase.

Sample Problems

Questions from this topic will typically present a line of LISP code or a short sequence of statements and ask what is the value of the (final) statement.

LISP

Evaluate the following expression.

(MULT (ADD 6 5 0) (MULT 5 1 2 2) (DIV 6 (SUB 2 5))) =

[0/2]

LISP

What is the value of the following LISP expression?

(CDR (CAR (CDR ‘((b c) (a d f) (d))))) =

[0/2]

LISP

Simplify the following expression:

(CAR (CAR (CDR (CDR (CDR ‘(1 (2 3) 4 ((5 6) (7 8) 9)))))))

[0/2]